package lib.combination;

import java.util.Arrays;
import java.util.Iterator;

/**
 * Get all permutations of the given object array.
 * 
 * @author <a href="www.sureinterview.com">SureInterview</a>
 * 
 * @param <T>
 *            Comparable objects.
 */
public class PermutationImpl<T extends Comparable<T>> extends Permutation<T> {

	boolean firstElemntOut;

	int n; // total number

	T[] objList; // the object list

	/**
	 * Setup the object array to be permuted.
	 * 
	 * @param obj
	 *            the object list
	 */
	public PermutationImpl(T[] obj) {
		super();
		if (obj == null || obj.length < 2)
			throw new ExceptionInInitializerError("Invalid parameters.");

		// initialize
		objList = obj;
		this.n = obj.length;
		firstElemntOut = false;
	}

	@Override
	public T[] get(Long index) {
		// adjust to 1-based.
		index++;

		// parse the index to {n-1, n-2, ... 3, 2, 1, 0}-based number.
		// For example, 10 = {1, 1, 1, 1, 0}. The meaning of each digits is the
		// number of digits on the left greater than current digit. For example,
		// in object list {a, b, d, c, e}, The corresponding index = {0, 0, 1,
		// 0, 0}. Because c has d on the left.
		Integer[] permArr = new Integer[n];
		for (int i = n - 1; i >= 0; i--) {
			permArr[i] = (int) ((index % (n - i)));
			index /= n - i;
		}

		// keep objList2 as a reference.
		T[] objList2 = Arrays.copyOf(objList, n);

		for (int objIdx = 0; objIdx < n; objIdx++) {
			int pos = 0;

			// get current object obj and find its current position in the
			// object list.
			T obj = objList2[objIdx];
			for (int i = 0; i < n; i++) {
				if (obj.equals(objList[i])) {
					pos = i;
					break;
				}
			}

			// the number of objects in reversed order (objects on the left and
			// greater than current object.)
			int revOrd = permArr[objIdx];
			for (int i = 0; i < n; i++) {
				// no object in reversed order. done.
				if (revOrd <= 0) {
					break;
				}

				// pass if the objects in list are smaller than current obj
				if (obj.compareTo(objList[i]) >= 0) {
					continue;
				}

				// move to larger objects to the left to fulfill "revOrd" number
				// of objects in reversed order.
				if (i > pos) {
					objList[pos] = objList[i];
					pos = i;
				}
				revOrd--;
				if (revOrd <= 0) {
					// put obj back for the last one
					objList[pos] = obj;
					break;
				}
			}
		}
		return objList;
	}

	@Override
	public boolean hasNext() {
		for (int k = n - 2; k >= 0; k--) {
			if (objList[k].compareTo(objList[k + 1]) < 0)
				return true;
		}
		return false;
	}

	@Override
	public Iterator<T[]> iterator() {
		return this;
	}

	/**
	 * Get the index-th permutation (0-based)
	 * 
	 * @see <a
	 *      href="http://en.wikipedia.org/wiki/Permutation#Systematic_generation_of_all_permutations"
	 *      >Permutation in Wiki</a>
	 * @param index
	 *            0-based index
	 * @return the permuted object array
	 */
	@Override
	public T[] next() {

		if (!firstElemntOut) {
			firstElemntOut = true;
			return objList.clone();
		}

		// see the wiki page for detailed explanation.
		// http://en.wikipedia.org/wiki/Permutation#Systematic_generation_of_all_permutations

		// find the least significant reversed order
		int k = n - 2;
		for (; k >= 0; k--) {
			if (objList[k].compareTo(objList[k + 1]) < 0) {
				break;
			}
		}

		int l = n - 1;
		for (; objList[k].compareTo(objList[l]) >= 0; l--) {
			;
		}

		// swap it.
		swap(k, l);

		// make k+1..n-1 to be in ascending order. That is, the next smallest
		// permutation in dictionary order.
		for (int i = k + 1, j = n - 1; i < j; i++, j--) {
			swap(i, j);
		}

		return objList;
	}

	@Override
	public void remove() {
		throw new UnsupportedOperationException();
	}

	private void swap(int i, int j) {
		T tmp = objList[i];
		objList[i] = objList[j];
		objList[j] = tmp;
	}
}
